1. Field of the Invention
This invention relates to an asynchronous decoder circuit. More specifically, this invention relates to an asynchronous decoder circuit that operates on data coded using a variable-length coding technique, such as Huffman coding.
2. Discussion of the State of the Art
Huffman coding is a lossless coding technique that replaces fixed-length symbols with variable-length codes. Huffman codes are entropy-based, meaning that short codes are assigned to frequently occurring symbols and longer codes are assigned to less frequently occurring symbols. In addition, Huffman codes are prefix codes, meaning that each code has the property that appending additional bits to the end of the code never produces another valid code. Advantageously, Huffman coding has been used for the compression of data.
In most applications utilizing Huffman-coded data, the speed and size of a Huffman decoder are important. For example, Huffman decoders may be used in compressed-code embedded systems. A compressed-code embedded system is a microprocessor or microcontroller-based system in which instructions are stored in compressed form in memory, then are decompressed when brought into a cache. As a result, a significant reduction in instruction memory size may be obtained. The design of a decompression circuit for these systems is highly constrained. In particular, the circuit must be very fast (since it is on the critical path between the processor and memory) and must also be very small (otherwise the savings in instruction memory will be lost to the area increase due to the decompression circuit).
As another example, Huffman decoders are also used in decompressing audio and video under the MPEG-2 image coding standard from the Moving Picture Experts Group (a working group of ISO). Under MPEG-2, a Huffman decoder is required to decode data at a rate of 100 Mbits/sec or greater to maintain a sufficient quality of audio and video.
Thus far, there have been two commonly-used approaches to the design of Huffman decoders, both of which are synchronous (that is, the decoders are synchronized to an external system clock). In the first approach, known as the constant-input-rate approach, the input data stream is processed at a rate of one bit per clock cycle by traversing a Huffman code tree through the use of a finite state machine. To achieve a high performance using this type of design requires a very fast clock, introducing many very difficult high-speed circuit problems. In fact, it is unlikely that a state machine of adequate complexity can be designed to run at the speeds required by the constant-input-rate approach on a silicon wafer produced by some semiconductor processes, such as a 0.8 μ CMOS process. To avoid the problems caused by the use of very high-speed clocks, multiple state transitions may be combined into a single cycle. As multiple state transitions are combined, however, the complexity and circuit area of the decoder increase approximately exponentially with respect to the increased performance per clock cycle.
A second commonly-used approach to the design of Huffman decoders is a constant-output-rate approach. In this approach, a portion of the input data stream, at least as long as the longest input symbol, is translated into an output symbol on each clock cycle. One disadvantage to this approach is that it requires a complex shifting network to remove variable length symbols from the input data stream, as well as more complex symbol detection circuitry than the constant-input-rate approach. This complexity has a negative impact on the circuit area of the design.
Another disadvantage of the constant-output-rate approach is that the length of the critical path is dominated by the time to detect and decode the longest input symbol. Thus, the vast majority of cycles are limited by a very infrequent worst-case path. Furthermore, the input data buffer and shifting network must be wide enough to store and shift the longest of the input symbols, which is inefficient since the most frequently occurring input symbols will be shorter than the longest input symbol.
In sum, each of the two commonly-used approaches to the design of Huffman decoders requires compromises and trade-offs between high-speed and low-area implementations. Accordingly, there exists a need for an improved Huffman decoder design that provides a higher ratio of performance to circuit area than is possible with existing circuit designs.